// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.algorithms;

import java.util.Arrays;
import java.util.Iterator;

import com.thalesgroup.graphFramework.core.Edge;
import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;
import com.thalesgroup.graphFramework.core.VerticesPartition;

import com.thalesgroup.graphFramework.collections.Pair;

public class StronglyConnectedComponentComputer {

	protected static enum Color {
		WHITE, GREY, BLACK
	}

	public <V, E> VerticesPartition<V, E> compute(final Graph<V, E> graph) {
		final Pair<Integer, Vertex<V, E>>[] ends = forwardPP(graph);
		return backwardPP(graph, ends);
	}

	protected <V, E> Color[] initColor(final Graph<V, E> graph) {
		final Color[] colors = new Color[graph.getVerticesSize()];
		Arrays.fill(colors, Color.WHITE);
		return colors;
	}

	@SuppressWarnings("unchecked")
	protected <V, E> Pair<Integer, Vertex<V, E>>[] forwardPP(
			final Graph<V, E> graph) {
		final Color[] colors = initColor(graph);
		int time = 0;
		final Pair<Integer, Vertex<V, E>>[] ends = new Pair[graph.getVerticesSize()];
		for(Iterator<Vertex<V,E>> iu=graph.getVertices(); iu.hasNext();) {
			Vertex<V,E> u=iu.next();
			if (Color.WHITE.equals(colors[u.getIndex()])) {
				time = forwardVisit(u, time, ends, colors);
			}
		}
		return ends;
	}

	protected <V, E> int forwardVisit(final Vertex<V, E> u, final int time,
			final Pair<Integer, Vertex<V, E>>[] ends, final Color[] colors) {
		int resultTime = time;
		colors[u.getIndex()] = Color.GREY;
		for(Iterator<Edge<V,E>> ie=u.getOuts(); ie.hasNext();) {
			Edge<V,E> e=ie.next();
			final Vertex<V, E> v = e.getOut();
			if (Color.WHITE.equals(colors[v.getIndex()])) {
				resultTime = forwardVisit(v, resultTime, ends, colors);
			}
		}
		colors[u.getIndex()] = Color.BLACK;
		resultTime++;
		ends[u.getIndex()] = Pair.new_(-resultTime, u);
		return resultTime;
	}

	protected <V, E> VerticesPartition<V, E> backwardPP(
			final Graph<V, E> graph, final Pair<Integer, Vertex<V, E>>[] ends) {
		final Color[] colors = initColor(graph);
		final VerticesPartition<V, E> partition = new VerticesPartition<V, E>(
				graph);
		Arrays.sort(ends);
		for (int i = 0; i < ends.length; i++) {
			final Vertex<V, E> u = ends[i].getSecond();
			if (Color.WHITE.equals(colors[u.getIndex()])) {
				backwardVisit(u, partition, colors);
			}
		}
		return partition;
	}

	protected <V, E> void backwardVisit(final Vertex<V, E> u,
			final VerticesPartition<V, E> partition, final Color[] colors) {
		colors[u.getIndex()] = Color.GREY;
		for(Iterator<Edge<V,E>> ie=u.getIns(); ie.hasNext();) {
			Edge<V,E> e=ie.next();
			final Vertex<V, E> v = e.getIn();
			if (Color.WHITE.equals(colors[v.getIndex()])) {
				if (!partition.findLeader(u).equals(partition.findLeader(v))) {
					partition.union(u, v);
				}
				backwardVisit(v, partition, colors);
			}
		}
		colors[u.getIndex()] = Color.BLACK;
	}

}
